#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#include "linklist.h"

int listhead_init(listhead_t **mylist, int size)
{
	*mylist = malloc(sizeof(listhead_t));
	if (NULL == *mylist)
		return -1;
	// (*mylist)->next = NULL;
// 	(*mylist)->head.data = NULL; // 没有用，为了匹配数据类型
	(*mylist)->head.next = NULL;
	(*mylist)->size = size;
	(*mylist)->numbers = 0;

	return 0;
}

static struct node_st * __create_node(const void *data, int size)
{
	struct node_st *me = NULL;

	me = malloc(sizeof(struct node_st) + size);
	if (NULL == me)
		return NULL;
	/*
	me->data = malloc(size);
	if (NULL == me->data) {
		free(me);
		me = NULL;
		return NULL;
	}
	*/
	memcpy(me->data, data, size);
	me->next = NULL;

	return me;
}

int list_insert(listhead_t *mylist, const void *data)
{
	struct node_st *p = NULL;

	p = __create_node(data, mylist->size);
	if (NULL == p)
		return -1;

	p->next = mylist->head.next;
	mylist->head.next = p;
	mylist->numbers++;

	return 0;
}

int list_insert_tail(listhead_t *mylist, const void *data)
{
	struct node_st *p = NULL;
	struct node_st *cur = NULL;

	p = __create_node(data, mylist->size);
	if (NULL == p)
		return -1;

	if (NULL == mylist->head.next) {
		mylist->head.next = p;
	} else {
		for (cur = mylist->head.next; cur->next != NULL; cur = cur->next)	
			;
		cur->next = p;
	}
	mylist->numbers++;

	return 0;
}

void list_traval(const listhead_t *mylist, pri_t pri)
{
	struct node_st *cur = NULL;

	for (cur = mylist->head.next; cur != NULL; cur = cur->next)
		pri(cur->data);
}

static int  __always_cmp(const void *data, const void *key)
{
	return 0;
}

void list_destroy(listhead_t **mylist)
{
	struct node_st *cur, *bebind;

	if (*mylist == NULL)
		return ;

	while (!list_empty(*mylist)) {
		list_delete(*mylist, NULL, __always_cmp);
	}

	free(*mylist);
	*mylist = NULL;
}

/*
 与key匹配的结点的前驱的地址
 第一个数据结点的前驱头结点
 	头结点的地址类型是listhead_t *
	数据结点的地址类型是struct node_st *
 */
static struct node_st *__find_prev(const listhead_t *mylist, const void *key, cmp_t cmp)
{
	struct node_st *prev, *cur;

	// 指向头结点
	prev = (struct node_st *)&mylist->head;  // &mylist->head == mylist
	cur = prev->next;
	while (cur != NULL) {
		if (0 == cmp(cur->data, key))
			return prev;
		prev = cur;
		cur = cur->next;
	}
	return NULL;
}

int list_delete(listhead_t *mylist, const void *key, cmp_t cmp)
{
	struct node_st *p, *del;

	if (list_empty(mylist))
		return -1;

	p = __find_prev(mylist, key, cmp);
	if (NULL == p)
		return -1;
	del = p->next;
	p->next = del->next;
	del->next = NULL;
	free(del);
	del = NULL;

	mylist->numbers --;

	return 0;
}

int list_empty(const listhead_t *mylist)
{
	return mylist->head.next == NULL;
}

void *list_search(const listhead_t *mylist, const void *key, cmp_t cmp)
{
	struct node_st *prev = __find_prev(mylist, key, cmp);
	if (NULL == prev)
		return NULL;
	return (void *)prev->next->data;
}

/*
   void list_reverse(listhead_t *mylist)
{
	struct node_st *p = NULL, *fetch;	

	if (list_empty(mylist))
		return ;
	p = mylist->head.next;
	while (p->next != NULL) {
		fetch = p->next;	
		p->next = fetch->next;
		// 头插
		fetch->next = mylist->head.next;
		mylist->head.next = fetch;
	}

}
*/

void *list_mid_node(const listhead_t *mylist)
{
	struct node_st *fast, *slow;

	if (list_empty(mylist))
		return NULL;

	for (fast = slow = mylist->head.next; fast != NULL && fast->next != NULL; \
			slow = slow->next, fast = fast->next->next)
		;
	return slow->data;
}

static struct node_st *__meet(const listhead_t *mylist)
{
	struct node_st *fast, *slow;

	if (list_empty(mylist))
		return NULL;
	fast = slow = mylist->head.next; 
	while (fast != NULL && fast->next != NULL) {
		slow = slow->next, fast = fast->next->next;
		if (fast == slow)	
			return fast;
	}

	return NULL;	
}

int list_cycle(const listhead_t *mylist)
{
	if (__meet(mylist) == NULL)
		return 0;
	return 1;
}

void *list_enter(const listhead_t *mylist)
{
	struct node_st *first;
	struct node_st *m = __meet(mylist);
	if (NULL == m)
		return NULL;

	first = mylist->head.next;
	while (first != m) {
		first = first->next;	
		m = m->next;
	}

	return m->data;
}



